#include<iostream>
using namespace std;



struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};

class Solution {
public:
    int nodeNum(struct TreeNode* head) {
        return recursion(head);
    }

    //获取树深度
    int getDepth(const struct TreeNode* head) {
        int depth = 0;
        auto thead = head;
        while(thead != nullptr) {
            depth++;
            thead = thead->left;
        }
        return depth;
    }

    //求取二叉树节点数目
    //head:二叉树头节点 level:当前节点层数  rootDepth:根树深度
    //return:head为root二叉树节点数目
    int recursion(struct TreeNode* head) {
        int rootDepth = getDepth(head);
        if(rootDepth == 0 || rootDepth == 1) {
            return rootDepth;
        }
        //右树深度
        int rightDepth = getDepth(head->right);
        if(rightDepth == rootDepth - 1) {
            cout << "右树到底 root:" << head->val << endl;
            //右树到底 左树满 深度rightDepth
            int leftNum = (1 << rightDepth) - 1;
            int rightNum = recursion(head->right);
            return leftNum + rightNum + 1;
        } else {
            cout << "右树不到底 root:" << head->val << endl;
            //右树不到底 右树满 深度rightDepth
            int leftNum = recursion(head->left);
            int rightNum = (1 << rightDepth) - 1;
            return leftNum + rightNum + 1;
        }
    }

};

int main() {

}